Probe points are frequently captured by global positioning systems (“GPS”), navigation systems or the like. Each probe point is associated with a location, such as may be expressed in terms of latitude and longitude. Some probe points are also associated with a heading and a speed at which the GPS system or the navigation system was moving at the time at which the probe point was captured.
In some instances, such as within a region for which a map consisting of a plurality of road segments has been created, the probe points may be matched to the map in order to identify the location along a road segment at which the probe point was captured. Map matching may be performed in real time, such as by navigation systems in order to identify the location of the probe point relative to the road segments represented by the map. For example, navigation systems mounted within a vehicle may perform real time map matching in order to depict the relative position of a probe point upon a map, thereby illustrating the current location of the vehicle. Map matching for real time applications may only utilize the path of probe points up to the most recent probe point since those are the only probe points that are known. Alternatively, map matching may rely upon post-processing, such as in instances in which the probe points captured by a plurality of GPS systems or navigation systems are matched to the road segments represented by a map for traffic estimation or other purposes. The accuracy of the map matching provided by post-processing may be improved relative to the map matching for real time applications since probe points captured subsequent in time to the probe point currently being processed are also known and may be referenced during the post-processing.
A variety of probe-centric map matching techniques have been developed. These map matching techniques include map matching techniques that utilize geometric analysis including point-to-point analysis, point-to-curve analysis and trajectory techniques. Other map matching techniques utilize a topological analysis of the road network to improve accuracy and performance. Some map matching techniques utilize probabilistic map-matching algorithms. The probabilistic map-matching algorithms attempt to identify the most probable road segment in some confidence region about a respective probe point. Additionally or alternatively, probabilistic map-matching algorithms may attempt to identify the most probable path in addition to the most probable road segment. The probabilistic map-matching algorithms may include, for example, Viterbi and hidden Markov model techniques. Further, map-matching techniques may include other types of map-matching algorithms including those that utilize Kalman and extended Kalman based techniques and those that utilize particle filters.
Whether performed in real time or as a post-processing technique, map matching has been a probe-centric process in which each probe point is analyzed to identify the closest road segment and the projection of the probe point onto the closest road segment. In order to identify the closest road segment, a separate spatial search is generally conducted for each probe point; even in instances in which a probe point is spaced a substantial distance from any road segment. Thus, the number of spatial searches to be conducted is generally proportional to the number of probe points.
Spatial searches are computationally expensive. For example, probe-centric map matching techniques for large probe data sets, such as millions of probe points, can incur substantial execution time and costs since the number of spatial searches is proportional to the number of probe points. Thus, map matching and, in particular, the spatial searches for each of the probe points may become a limiting factor at least for real time applications.